package monotonous_queue;

import java.util.Deque;
import java.util.LinkedList;
import java.util.PriorityQueue;

/**
 * 滑动窗口最大值 <br />
 * 算法：单调队列
 *
 * @author yzh
 * @version 1.0
 * @date 2022/8/30 22:12
 */
public class _239 {

    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] ans = new int[n - k + 1];
        Deque<Integer> queue = new LinkedList<>();
        for (int i = 0, idx; i < n; i++) {
            while (!queue.isEmpty() && nums[i] > nums[queue.peekLast()]) queue.pollLast();
            queue.addLast(i);
            idx = i - k + 1;
            if (idx >= 0) {
                if (queue.peekFirst() == idx - 1) queue.pollFirst();
                ans[idx] = nums[queue.peekFirst()];
            }
        }
        return ans;
    }

    public static int[] maxSlidingWindow_queue(int[] nums, int k) {
        int n = nums.length;
        int[] ans = new int[n - k + 1];
        PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> b[1] - a[1]);
        for (int i = 0; i < n; i++) {
            q.offer(new int[]{i, nums[i]});
            if (i >= k - 1) {
                while (q.peek()[0] <= i - k) q.poll();
                ans[i - k + 1] = q.peek()[1];
            }
        }
        return ans;
    }

}
